/*
2022-3-13
https://leetcode-cn.com/problems/count-artifacts-that-can-be-extracted/
*/ 
class Solution {
public:
    int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
        int ans=0;
        int a[1010][1010];
        int sum[1010][1010];
        memset(a,0,sizeof a);
        memset(sum,0,sizeof sum);
        for(auto tump:dig)
        {
            a[tump[0]+1][tump[1]+1]=1;
        }

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
            }
        for(auto tump:artifacts)
        {
            int i=tump[0]+1,j=tump[1]+1,x=tump[2]+1,y=tump[3]+1;
            if((x-i+1)*(y-j+1)==sum[x][y]-sum[x][j-1]-sum[i-1][y]+sum[i-1][j-1]) ans++;
        }
        return ans;
    }
};
